package 树;

import 抽象数据类型.TreeNode;

/**
 * @description: bts转化为循环双向链表
 * @author: ywk
 * @date: 2020-06-27
 */
public class BST2DLL {
    public static void main(String[] args) {

    }

    TreeNode BST2DLL(TreeNode root) {

        return root;
    }
    TreeNode BST2DLL(TreeNode root, TreeNode lTail) {
        TreeNode left,ltail = null,right,rtail = null;
        if (root == null) {
            ltail = null;
            return null;
        }
        left = BST2DLL(root.getLeft(), ltail);
        right = BST2DLL(root.getRight(), rtail);
        root.setLeft(ltail);
        root.setRight(right);
        if (right == null) {
            ltail = root;
        }else{
            right.setLeft(root);
            ltail = rtail;
        }
        if (left == null) {
            return root;
        }else{
            ltail.setRight(root);
            return left;
        }

    }
}
